It has been shown that it is impossible to achieve both stringent end-to-enddeadline and reliability guarantees in a large network without having completeinformation of all future packet arrivals. In order to maintain desirableperformance in the presence of uncertainty of future packet arrivals, commonpractice is to add redundancy by increasing link capacities. This paper studiesthe amount of capacity needed to provide stringent performance guarantees. Wepropose a low-complexity online algorithm and prove that it only requires asmall amount of redundancy to guarantee both end-to-end deadline andreliability. Further, we show that in large networks with very high reliabilityrequirements, the redundancy needed by our policy is at most twice as large asa theoretical lower bound. Also, for practical implementation, we propose afully distributed protocol based on the previous centralized policy. Withoutadding redundancy, we further propose a low-complexity order-optimal onlinepolicy for the network. Simulation results also show that our policy achievesmuch better performance than other state-of-the-art policies.
展开▼
